package leetcode_1201_1300;

import java.util.*;

public class LeeCode_1224 {
    public static void main(String[] args) {
        System.out.println(maxEqualFreq(new int[]{2, 2, 1, 1, 5, 3, 3, 5}));
        System.out.println(maxEqualFreq(new int[]{1,1,1,2,2,2,3,3,3,4,4,4,5}));
        System.out.println(maxEqualFreq(new int[]{10,2,8,9,3,8,1,5,2,3,7,6}));
        System.out.println(maxEqualFreq(new int[]{1,2}));
        System.out.println(maxEqualFreq(new int[]{1,1}));
    }
    private static int maxEqualFreq(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, Integer> map2 = new HashMap<>();
        int ans = 1;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int pre = map.getOrDefault(num, 0);
            map.put(num, pre + 1);

            Integer pre2 = map2.getOrDefault(pre, -1);
            if (pre2 == 1){
                map2.remove(pre);
            }else if (pre2 != -1){
                map2.put(pre, pre2 - 1);
            }
            map2.put(pre + 1, map2.getOrDefault(pre + 1, 0) + 1);
            if (map2.size() == 2){
                boolean flag = true;
                int k1 = 0, k2 = 0;
                for (Integer key : map2.keySet()) {
                    if (flag) {
                        k1 = key;
                        flag = false;
                    } else {
                        k2 = key;
                    }
                }
                int max = Math.max(k1, k2);
                int min = Math.min(k1, k2);
                if (min == 1 && map2.get(min) == 1)
                    ans = Math.max(ans, i + 1);
                if (max - min == 1 && map2.get(max) == 1)
                    ans = Math.max(ans, i + 1);
            }else if (map2.size() == 1){
                for (Integer key : map2.keySet()) {
                    if (key == 1 || map2.get(key) == 1)
                        ans = Math.max(ans, i + 1);
                }
            }
        }
        return ans;
    }
}